The present invention relates generally to data communication switching systems and more particularly relates to a cross bar switching matrix having improved broadcast performance due to the utilization of broadcast buffering.
Increasing reliance is being placed on data communication networks to carry increasing amounts of data. In a data communications network, data is transmitted end to end in groups of bits called packets, frames, cells, messages, etc. depending on the type of data communication network. For example, Ethernet networks transport frames, X.25 and TCP/IP networks transport packets and ATM networks transport cells. Regardless of what the data unit is called, each data unit is defined as part of the complete message that the higher level software application desires to send from a source to a destination. Alternatively, the application may wish to send the data unit to multiple destinations.
Currently, many switching systems utilize switching fabrics or matrixes that are designed to switch variable length packets of data. The variable length of packets in these switching systems, however, offer larger and less predictable switching delays as packet switching is more complex than fixed length packet switching.
The transmission of data to a single destination is termed unicast data while the transmission of data to all destinations is termed broadcast data. The transmission of data to a select number of destinations larger than one is termed multicast data. In an example switching system, each call connection within the switch has associated with it a routing tag or equivalent that functions to identify the destination for the packet.
For unicast connections, the routing information identifies a single destination for the packet. For broadcast connections, the routing information identifies the packet as a broadcast packet that is to be distributed to all output ports. For multicast connections, the routing information identifies several destinations for the packet.
A majority of data communication networks today attempt to not lose even a single bit of information in transmitting data from one point to another. In order to achieve such high levels of performance and low error rates, the network equipment is constructed with relatively large sized queues. The large queues are needed in order to handle the accumulation of packets without overflowing the queues. An overflow of a queue will result in packets being lost, i.e., dropped. Packets may be dropped at the source queue if the destination is full and thus cannot receive additional packets. In this case, the source queue fills up and at some point will overflow, with consequent packet loss.
A problem arises, however, with the transmission of broadcast packets through the switching matrix. In prior art switching systems, the switch must wait until the matrix tracks are cleared before a broadcast packet can be transmitted through the switch. All the output ports of the switch matrix must be free before the broadcast packet can be transmitted. This results in very large delays, which greatly reduces the efficiency and throughput of the switch matrix. The following example illustrates this problem.
A block diagram illustrating an example prior art crossbar switch matrix capable of handling unicast, broadcast and multicast traffic is shown in FIG. 1. The switching system, generally referenced 10, comprises a plurality of input/output (I/O) interface (I/F) cards 12 having a plurality of PHY interfaces, labeled 1 through M, and a plurality of outputs, labeled 1 through N. The system 10 further comprises an Nxc3x97N crossbar switch matrix 14 having N input ports and N output ports. The N outputs of the I/F cards 12 are coupled to the N input ports of the switch matrix 14. The N output ports of the switch matrix 14 are input back to the I/F cards 12. A controller 16 functions to control the configuration of the switch matrix 14 at any particular point in time via one or more control lines 18 labeled CNTRL.
The crossbar switch is required to switch the entire set of input ports to the output ports in accordance with configuration information from the controller 16. The controller 16 is responsible for providing the appropriate configuration information to the crossbar switch matrix 14 at the correct time. The crossbar switch 14 performs the switching operation in accordance with the switching information provided by the controller. In the event of a broadcast packet to be transmitted from any of the I/F cards, the configuration controller 16 provides the appropriate switching commands which cause the broadcast packet to be transmitted to all the output ports. This is achieved by the issuance of the suitable configuration commands to each I/F card. All I/F cards (except the one transmitting the broadcast packet) and all the input ports will be in the idle state for a broadcast transmission to occur.
A block diagram illustrating the I/O interface (I/F) card of the prior art switch in more detail is shown in FIG. 2. The I/O card 20 comprises a PHY interface 24 to/from a physical connection 22. The I/O card also comprises a controller/packet processor 26, memory 27, output queues 28, input queue 30, host interface 25 and backplane interface 29.
The I/O card comprises N output queues 28, labeled Q1 through QN, one queue corresponding to each output port of the switch matrix. An additional broadcast queue, labeled QBC, is also included for buffering packets to be broadcast to all output ports. Note that the queues may optionally be implemented using the memory 27. The queues interface to the switch matrix via a backplane interface 29.
The PHY interface 24 is coupled to a controller/packet processor 26 that functions to receive packets and route them to the appropriate output queue. Note that the PHY interface 24 may be adapted to handle electrical or optical signals, e.g., OC-3, OC-12, SONET, 1000BaseT, etc.
In operation, the format of the received signal is converted to packets and input to the packet processor 26. The packet processor 26 functions to process the data destined to the ingress of the switching matrix and to process the data output from the egress of the switching matrix. The packet processor, in accordance with the connection information, determines a destination output port for data received over the PHY I/O channel. For unicast transmission, the packet processor places the packet in one of N queues 28 corresponding to one of N output ports. For broadcast connections, the packet is placed in the broadcast queue QBC for broadcast to all output ports simultaneously.
When packets are output of the switch matrix, they return to the I/F card corresponding to the output port. A backplane interface 29 interfaces the input and output queues to the switch matrix. Packets destined to an output queue on a particular I/F card, are input to the output queue Qo 30 via the backplane interface 29. The packet is then input to the packet processor 26 and output to the PHY via the PHY interface 24.
Note that a unicast queue is a physical queue that accumulates packets designated to be transmitted to a single destination queue and is associated with a point to point connection. A broadcast queue is a physical queue that accumulates packets designated to be transmitted to all destination queues
A disadvantage of this prior art switching architecture is that the transmission of broadcast packets occurs only when all the input ports are in the idle state, i.e., they are not in the middle of transmitting a packet of data. In addition, during the transmission of a broadcast packet, all the I/F cards, except the one transmitting the broadcast packet, are also in the idle state. Since the switch is constructed to transmit variable length packets, the waiting time until all the I/F cards and input ports are in the idle state, i.e., have completed their current packet transmissions, is also variable and may be very long. An illustration of this problem is provided below.
A diagram illustrating the timing of the transmission of packets through a prior art switch matrix before and after a broadcast packet is scheduled for transmission is shown in FIG. 3. Assume that prior to the point in time represented by reference arrow 40 in FIG. 3, that each input port is in the midst of receiving a data stream comprising variable length packets. Each line represents a different egress output port from the switch matrix. The output ports comprise output ports #1 through output ports #N but only output ports #1 through #5 and #N are shown for clarity sake. The switch matrix creates a traffic stream from input ports to output ports.
Assume also that at the time represented by reference arrow 40, the controller is notified of a broadcast packet ready for transmission on one of the I/F cards. At this point, the controller ceases starting any new packet transmissions and waits until the busy ports finish their transmissions of the current packet. After the last port has completed transmission, the controller configures the switch matrix to transmit the broadcast packet to all the output ports. Once the broadcast packet has completed transmission through the switch, new packets queued up in each of the I/F cards begin transmission through the switch matrix to the output ports and normal unicast packet flow resumes.
With reference to FIG. 3, the waiting time TW can be relatively large compared to the transmission time of some of the packets. The controller must wait for the longest length packet to finish transmission before sending the broadcast packet. The waiting time TW in this case extends from the end of the packet output from port #5 to the end of the packet output from port #4. Only at that point can the broadcast packet 42 be transmitted through the switch. The time of transmission of the broadcast packet is denoted by TBC. The waiting time TW, i.e., unutilized slot time, before transmitting the broadcast packet causes a large decrease in performance. This problem is even more acute when the switch is capable of operating at very high speeds.
The present invention is a crossbar switching matrix that improves the transmission of variable length broadcast packets. The type of environment suitable for application of the present invention is any data switching device that is adapted to switch variable length units of data, e.g., packets, frames, cells, etc. The invention provides for greatly reduced latency when transmitting broadcast packets through the switch matrix.
The invention achieves this by halting unicast traffic regardless of the state of packet completion, i.e., in the middle of packet transmission operations, and immediately beginning transmission of the broadcast packet. Once the broadcast packet has finished transmission, unicast packet transmission is resumed without any loss of data.
A unicast buffer is utilized to store the unicast packet while the broadcast packet is being transmitted. A broadcast buffer is used to buffer the broadcast packet as it egresses from the switch matrix. In this fashion, the broadcast information is given high priority and passes quickly through the switch without the large delays associated with the prior art switch matrixes.
The invention is applicable to both electrical and optical switches, wherein in the latter case, the optical signals are converted to electrical signals before arriving at the crossbar matrix and are converted to optical signals after egressing from the crossbar matrix.
There is thus provided in accordance with the invention a crossbar switching system for use with variable length data packets, comprising an Nxc3x97N crossbar switch matrix comprising N input ports and N output ports, the switch matrix adapted to couple data present at any input to any output port in accordance with switch configuration commands, N interface (I/F) circuits, each I/F circuit coupled to a corresponding input port on the switch matrix, N broadcast/unicast (BC/UNI) buffer circuits, each BC/UNI buffer circuit coupled to a corresponding output port on the switch matrix, the BC/UNI buffer circuit comprising, a unicast buffer adapted to store and forward unicast packets output of the egress of the switch matrix to a corresponding I/F circuit and, a broadcast buffer adapted to store a broadcast packet output of the egress of the switch matrix, a controller adapted to steer unicast packet data to the unicast buffer, the controller operative to halt the transmission of unicast packet data to the unicast buffer in each of N BC/UNI buffer circuits upon the arrival of a broadcast packet, wherein the broadcast packet data output of the switch matrix is stored in the broadcast buffer in each of N BC/UNI buffer circuits and subsequently transmitted to each of the N I/F circuits and wherein the transmission of unicast packet data is resumed following the completion of transmission of the broadcast packet.
The BC/UNI buffer circuit further comprises, a 1 to 2 demultiplexor adapted to steer packet data output of the switch matrix to either the BC buffer or the UNI buffer and, a 2 to 1 multiplexor adapted to transmit the output of either the BC buffer or the UNI buffer in accordance with a select control.
There is also provided in accordance with the invention a broadcast (BC)/unicast (UNI) buffer apparatus for use with an Nxc3x97N crossbar switch matrix having N input ports and N output ports and adapted to switch variable length data packets, and N interface (I/F) circuits for interfacing physical ports to the switch matrix, the apparatus comprising, broadcast storage means adapted to store broadcast packet data output of the switch matrix, unicast storage means adapted to store unicast packet data output of the switch matrix, steering means operative to either store unicast packet data in the unicast storage means or broadcast packet data in the broadcast storage means, the steering means selecting either the unicast storage means or the broadcast storage means in accordance with a select signal, control means operative to halt the transfer and storage of unicast packet data to the unicast storage means upon the arrival of a broadcast packet, whereby the broadcast packet data is stored in the broadcast storage means and transmitted to the I/F circuit and wherein the transmission and storage of unicast packet data into the unicast storage means is resumed following the completion of transmission of the broadcast packet.
There is further provided in accordance with the invention, in a switching system including an Nxc3x97N crossbar switch matrix having N input ports and N output ports and adapted to switch variable length data packets, and N interface (I/F) circuits for interfacing physical ports to the switch matrix, a method of reducing the latency of broadcast packet transmission through the switching system, the method comprising the steps of storing unicast packet data in a unicast storage buffer in the absence of a broadcast packet to be transmitted through the switching system, halting the transmission of unicast packet data through the switch matrix and the subsequent storage of unicast packet data in the unicast storage buffer, storing broadcast packet data in a broadcast storage buffer immediately after it arrival to the switch matrix and resuming the transmission through the switch matrix and the subsequent storage in the unicast storage buffer of unicast packet data.